/**
 * @file graph.h
 * @author 张奕欣 3190105655 (3190105655@zju.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-12-02
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>
using namespace std;

/**
 * @brief 定义一个顶点的类
 * 输出顶点
 * @tparam VT 
 */
template <typename VT>
class graphVertex
{
private:
    VT _ver;
public:
    /**
     * @brief Construct a new graph Vertex object
     * 
     * @param d 
     */
    graphVertex( VT d) : _ver(d) {}
    /**
     * @brief retrun顶点
     * 
     * @return VT& 
     */
    VT ver() { return _ver; }
    VT ver() const { return _ver; }
    /**
     * @brief 使用 operator 重载运算符
     * 使重载后的运算符的使用方法与重载前一致；
     * @param v 
     * @return true 
     * @return false 
     */
    bool operator==(const graphVertex &v) const
    {
        if (this->_ver == v._ver)
            return true;
        else
            return false;
    }
    int in; //入度,有多少个边指向此结点
	int out;	//出度，有多少条边由此结点发散
    
};

/**
 * @brief 定义边
 * 
 * @tparam VT 
 */
template <typename VT>
class graphEdge
{
private:
    graphVertex<VT> _v1;
    graphVertex<VT> _v2;
    double _weight;

public:
    /**
     * @brief Construct a new graph Edge object
     * 
     * @param v1 
     * @param v2 
     * @param w 
     */
    graphEdge( graphVertex<VT> v1, graphVertex<VT> v2, double w=1)
        : _v1(v1), _v2(v2), _weight(w)
    {
    }
    /**
     * @brief 返回第一个顶点
     * 
     * @return graphVertex<VT>
     */
    graphVertex<VT> Vertex1() { return _v1; }
    graphVertex<VT> Vertex1() const { return _v1; }
    /**
     * @brief 返回第二个顶点
     * 
     * @return graphVertex<VT>
     */
    graphVertex<VT> Vertex2() { return _v2; }
    graphVertex<VT> Vertex2() const { return _v2; }
    /**
     * @brief 返回权重
     * 
     * @return double 
     */
    double weight() 
    {
        return _weight;
    }
    double weight() const 
    { 
        return _weight; 
    }
};


/**
 * @brief 使用邻接表存储
 * 
 * @tparam VT 
 */
template <typename VT>
class GraphAdList
{
private:
    vector<graphEdge<VT>> E;
    vector<list<graphVertex<VT>>> AdL;

public:
    /**
     * @brief Construct a new Graph object
     * 
     * @param _v 
     * @param _e 
     */
    GraphAdList( vector<graphVertex<VT>> _v , vector<graphEdge<VT>> _e )
    {
        for (auto x : _v)
            addgraphVertex(x);
        for (auto x : _e)
            addgraphEdge(x);
    }

    void addgraphEdge( graphEdge<VT> _e)
    {
        E.push_back(_e);
        for (int i = 0; i < AdL.size(); i++)
        {
            if (AdL[i].front() == _e.Vertex1())
            {
                AdL[i].push_back(_e.Vertex2());
            }
        }
    }
    

    void addgraphVertex( graphVertex<VT> _v)
    {
        list<graphVertex<VT>> L;
        L.push_back(_v);
        AdL.push_back(L);
    }

    void removeVertex( graphVertex<VT> _v)
    {
    }

    void removeEdge( graphEdge<VT> _e)
    {
    }
   
   //判断边是否存在
    bool existEdge(graphVertex<VT> _v1,graphVertex<VT> _v2) const;

    //顶点的入度和出度
    int inDegree(int theVertex) const;
    int outDegree(int theVertex) const;

    /**
     * @brief 输出所有的顶点
     * 
     */
    void listVertexes() 
    {
        for (int i = 0; i < AdL.size(); i++)
        {
            cout <<  AdL[i].front().ver() << "  ";
        }
        cout << endl;
    }
    
    /**
     * @brief 输出所有的边(u,v,w)的形式
     * 
     */
    void listEdges() 
    {
        for (int i = 0; i < E.size(); i++)
        {
            cout << "(" << E[i].Vertex1().ver() << " , "
                      << E[i].Vertex2().ver() << " , "
                      << E[i].weight() << ")" << endl;
        }
    }

};


/**
 * @brief 用邻接矩阵存储
 * 
 * @tparam VT 
 */
template <typename VT>
class GraphAdMatrix
{
private:
    vector<graphVertex<VT>> V;
    vector<graphEdge<VT>> E;
    vector<vector<double>> AdM;

public:
    /**
     * @brief Construct a new Graph object
     * 
     * @param _v 
     * @param _e 
     */
    GraphAdMatrix( vector<graphVertex<VT>> _v,  vector<graphEdge<VT>>  _e )
    {
        for (auto x : _v)
            addgraphVertex(x);
        for (auto x : _e)
            addgraphEdge(x);
    }

    /**
     * @brief Get the index object
     * 
     * @param v 
     * @return int 
     */
    int get_index( graphVertex<VT> v)
    {
        for (int i = 0; i < V.size(); i++)
        {
            if(v == V[i])
                return i;
        }
        return -1;
    }

    /**
     * @brief addgraphEdge
     * 
     * @param _e 
     */
    void addgraphEdge( graphEdge<VT> _e)
    {
        E.push_back(_e);
        int i = get_index(_e.Vertex1());
        int j = get_index(_e.Vertex2());
        AdM[i][j] = _e.weight();
        
    }
    

    /**
     * @brief  addgraphVertex
     * 
     * @param _v 
     */
    void addgraphVertex( graphVertex<VT> _v)
    {
        V.push_back(_v);
        AdM.resize(AdM.size() + 1);
        for (int i = 0; i < AdM.size(); i++)
        {
            AdM[i].resize(AdM.size() + 1);
        }
        
    }
    
    void removeVertex( graphVertex<VT> _v)
    {
    }

    void removeEdge( graphEdge<VT> _e)
    {
    }
    
    //判断边是否存在
    bool existEdge(graphVertex<VT> _v1,graphVertex<VT> _v2) const;

    //顶点的入度和出度
    int inDegree(int theVertex) const;
    int outDegree(int theVertex) const;

    /**
     * @brief listgraphVertexes
     * 
     */
    void listVertexes() 
    {
        for (int i = 0; i < V.size(); i++)
        {
            cout << V[i].ver() << " ";
        }
        cout << endl;
    }
    /**
     * @brief listgraphEdges
     * 
     */
    void listEdges() 
    {
        for (int i = 0; i < E.size(); i++)
        {
            cout << "(" << E[i].Vertex1().ver() << " , "
                    << E[i].Vertex2().ver() << " , "
                    << E[i].weight() << ")" << endl;
        } 
    }

};
